Snarkpack

$$ \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\e{\operatorname{e}} \gdef\g{\mathrm{g}} \gdef\k#1{\mathbf{#1}} $$

Recall a Groth16 verification with verification key $\p{\k D,\k E,\k F,\k G,\k L_i}$ and proof $\p{w_i, A, B, C}$. It's made to sum to zero and signs are absorbed into the constants.

$$ 0 = \e(A, B) + \e(\k E, \k F) + \e\p{ \sum_{i ∊ [0, p)} w_i ⋅ \k L_i, \k G} + \e\p{C, \k D} $$

Take $n$ proofs $\p{w_{ij}, A_j, B_j, C_j}$ and linearly combine them using $r_j$:

$$ \begin{aligned} 0 & = \sum_j r_j ⋅ \p{\e(A_j, B_j) + \e(\k E, \k F) + \e\p{ \sum_{i ∊ [0, p)} w_{ij} ⋅ \k L_i, \k G} + \e\p{C_j, \k D} } \\ & = \sum_j \e\p{r_j ⋅ A_j, B_j} + \e\p{\sum_j r_j ⋅ \k E, \k F} + \e\p{\sum_j \sum_{i ∊ [0, p)} r_j ⋅ w_{ij} ⋅ \k L_i, \k G} + \e\p{\sum_{i ∊ [0, p)} r_j ⋅ C, \k D} \\ \end{aligned} $$

Question. Can we proof soundness if the prover only provided $\sum_{i ∊ [0, p)} r_j ⋅ A_j$ and/or the equivalent for $B$ or $C$? Extreme case

$$ 0 = \e(A, B) + \e(\k E, \k F) + \e\p{\sum_j \sum_{i ∊ [0, p)} r_j ⋅ w_i ⋅ \k L_i, \k G} + \e\p{C, \k D} $$

where $r_j$ is derived by pseudorandom function from $w_{ij}$.


https://eprint.iacr.org/2021/529

Remco Bloemen
Math & Engineering
https://2π.com